package com.company.剑指offer每日刷题.专项版;

public class SingNumber {
    /**
     * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
     */
    public static void main(String[] args) {
        SingNumber obj = new SingNumber();
        int i = obj.singleNumber(new int[]{2, 2, 3, 3, 3, 2, 6});
        System.out.println(i);

    }

    /**
     * 方法：计算结果的每一个二进制位
     * 思路：我们求个数为1的那个数，可以依次求出这个数的每一个二进制位。
     * 因为除了唯一的那个数，其他的数都重复了三次，将这些重复数字的同一个二进制位累加之后，结果必定是0或者3的倍数，通过3整除求余之后，剩下的数就是唯一数的二进制数
     * 例如我们有 [2,2,2,4,4,4,5]  ，二进制化后：
     * 0 0 1 0
     * 0 0 1 0
     * 0 0 1 0
     * 0 1 0 1
     * 将它们的每一个位相加得：
     * 0 1 3 1
     */
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 1; i <= 32; i++) {
            short addNum = 0;
            for (int j = 0; j < nums.length; j++) {
                addNum += (nums[j] >> i) & 1;
            }
            addNum %= 3;
            res |= addNum << i;
        }
        return res;
    }
}
